package leetcode100

// TODO 双指针 | 链表 【-】 相交链表
// TODO https://leetcode.cn/problems/intersection-of-two-linked-lists/solution/160zhao-jiao-dian-by-cacia-f289/

func getIntersectionNode(headA, headB *ListNode) *ListNode {
	n1, n2 := getLen(headA), getLen(headB)
	d := n1 - n2
	if d > 0 {
		for i := 1; i <= d; i++ {
			headA = headA.Next
		}
	} else {
		for i := 1; i <= -d; i++ {
			headB = headB.Next
		}
	}

	for headA != nil && headB != nil {
		if headA == headB {
			return headA
		}
		headB = headB.Next
		headA = headA.Next
	}
	return nil
}

func getLen(node *ListNode) int {
	if node == nil {
		return 0
	}
	return 1 + getLen(node.Next)
}
